
%Dramatis Personae

%T = {t1,t2...tn} - set of targets
%C = {c1,c2...cn} - set of probabilities of defending for each target
%Uud(t) - defender payoff for an attack on uncovered target
%Ucd(t) - defender payoff for an attack on covered target


%UuaMax(t) - attacker max payoff for an attack on uncovered target
%UuaMin(t) - attacker min payoff for an attack on uncovered target
%UcaMax(t) - attacker max payoff for an attack on covered target
%UcaMin(t) - attacker min payoff for an attack on covered target

%R - maximum minimum value of attacker expected payoff

%c1(t) - min defender coverage for target t
%c2(t) - min attacker coverage for target t
%c3(t) - mysterious constraint: maximum attacker payoff

%e - error tolerance parameter for the binary search 
%m - count of available resources


function ISG_Algorithm()
   Tsize=9;
    m=5;
   e=0.0001;
   
    
   function initPayoffsVariables()
%   QmaxA=18;
%   QmaxD=20;
%   DefAmax=7;
%   DefDmax=8;
%   DistMax=2;    
 %  DefD=rand(1,Tsize)*DefDmax; 
 %  Qd=(DefDmax+1)+rand(1,Tsize)*QmaxD; 
   
 %  Uud=(-Qd-DefD); 
 %  Ucd=(-Qd+DefD);
   
  % Qa=(DefAmax+DistMax+1)+rand(1,Tsize)*QmaxA;
   
   %DefA=rand(1,Tsize)*DefAmax; 
   %Dist=rand(1,Tsize)*DistMax; 
   
  % UuaMax=Qa+DefA+Dist;
   %UcaMax=Qa-DefA+Dist;
  % UuaMin=Qa+DefA-Dist;
   %UcaMin=Qa-DefA-Dist;
   Uud=  [-35, -20,-15, -12,-15,-40,-35, -25, -14];
   Ucd=  [-25, -10, -8, -6,-10,-25,-15, -10,  -8];
   UuaMax=[15,  20,  5, 10, 8, 35, 25,  16,  12];
   UuaMin=[10,  15,  2,  8, 6, 25, 15,  12,  10];
   UcaMax=[10,  13,  2,  6, 5, 15, 10,   8,  8];
   UcaMin=[ 5,  10,  1,  4, 3, 10,  8,   4,   5];
   end

   C=zeros(Tsize,Tsize);
   payoffs=zeros(Tsize,1);
   initPayoffsVariables();
        Uud;Ucd;UuaMax;UcaMax;UuaMin;UcaMin;
   for m=1:Tsize
    [C(m,:),payoffs(m)]=calcISG(m);
    s=0;
   end
   X=1:Tsize;
   Y=payoffs';
   strValues = strtrim(cellstr(num2str(Y(:))));
   figure
   plot(X,Y,'.')
   text(X,Y,strValues,'VerticalAlignment','bottom');
   set(axesHandle, 'Xlim', 11, 'YLim', 12);
   
   
  
      
   
    function [C, midPoint] = calcISG(m)
        initPayoffsVariables();
        Uud;Ucd;UuaMax;UcaMax;UuaMin;UcaMin;
       C=zeros(Tsize,1);
       maxPayoff=0;
       minPayoff=min(Uud);
       while (maxPayoff-minPayoff)>e 
           midPoint=maxPayoff+(minPayoff-maxPayoff)/2;
           %midPoint=(maxPayoff-minPayoff)/2; 
           [ret,C]=feasibilityCheck(midPoint,m,C);
           if strcmp(ret,'true')
                minPayoff=midPoint;
           else
               maxPayoff=midPoint; 
           end
       end 
    end

   
   function [ret,C]=feasibilityCheck(midPoint,m,C)
        c1=zeros(1,Tsize);
        for t=1:Tsize
          c1(t)= get_c1(t);
        end
        for t=1:Tsize
            totalCov=c1(t);
            C(t)=c1(t);
            if C(t)>1
              continue  
            end
            R=get_R(c1(t),t);
            for tj=1:Tsize
                if(t==tj)
                    continue
                end
                c2=get_c2(R,tj);
                c3=get_c3(R,tj);
                minCov=max([c3,min(c1(t),c2)]);
                if minCov<0 || minCov>1
                    break
                end
                totalCov=totalCov+minCov;
                C(tj)=minCov;
            end
            if (minCov>=0 && minCov<=1) && totalCov<=m
                ret='true';
                return 
             end
        end
        
        
        
        ret='false';
        return 
        
        
        function c1=get_c1(t)
            %cash=1-(midPoint-Uud(t))/(Ucd(t)-Uud(t));
            cash=(midPoint-Uud(t))/(Ucd(t)-Uud(t));
            c1=max([0,cash]);        
        end
        function c2=get_c2(R,t)
            %cash=1-(R-UuaMax(t))/(UcaMax(t)-UuaMax(t));
            cash=(R-UuaMax(t))/(UcaMax(t)-UuaMax(t));
            c2=max([0,cash]); 
        end
        function c3=get_c3(R,t)
            %cash=1-(R-UuaMin(t))/(UcaMin(t)-UuaMin(t));
            cash=(R-UuaMin(t))/(UcaMin(t)-UuaMin(t));
            c3=max([0,cash]); 
        end
        function R=get_R(c1,t)
            R=(c1*UcaMin(t))+((1-c1)*UuaMin(t)-e);
        end
    end
   
end




